<?xml version="1.0" encoding="iso-8859-1"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
    "DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <link rel="stylesheet" type="text/css" href="html.css" />
    <title>JAS - Gr&ouml;bner bases book</title>
  </head>
  <body class="main">
    <h1>Gr&ouml;bner bases book algorithms and JAS methods</h1>

<p>
Summary of algorithms from the 
<a href="http://www.springer.com/mathematics/book/978-0-387-97971-7" target="gbb">Gr&ouml;bner bases</a> 
book and corresponding JAS classes and methods.
</p>


<h2>Gr&ouml;bner bases book algorithms</h2>

<p>
The JAS base package <code>edu.jas</code> name is omitted in the
following table.
JAS also contains improved versions of the algorithms which may be located through the links.
A short explanation of code organization with interfaces and several implementing classes
can be found in the <a href="design.html">API guide</a>.
</p>

<table border="1" cellpadding="3" summary="GB book to JAS summary" >
<tr>
<td>GB book algorithm</td>
<td>JAS interfaces, classes and methods</td>
<td>remarks</td>
</tr>

<tr>
<td>0.1&nbsp;<code>DIVINT</code></td>
<td><a href="doc/api/edu/jas/arith/BigInteger.html#divideAndRemainder(edu.jas.arith.BigInteger)" target="classFrame"><code>arith.BigInteger.divideAndRemainder</code></a>
</td>
<td>facade for <code>java.math.BigInteger.divideAndRemainder</code>
</td>
</tr>

<tr>
<td colspan="3">&nbsp;</td>
</tr>

<tr>
<td>2.1&nbsp;<code>DIV</code></td>
<td><a href="doc/api/edu/jas/structure/MonoidElem.html#divide(C)" target="classFrame"><code>structure.MonoidElem.divide</code></a>
and 
<a href="doc/api/edu/jas/structure/MonoidElem.html#remainder(C)" target="classFrame"><code>structure.MonoidElem.remainder</code></a>
</td>
<td>all classes which implement this interface
</td>
</tr>

<tr>
<td>2.2&nbsp;<code>DIVPOL</code></td>
<td><a href="doc/api/edu/jas/poly/GenPolynomial.html#divideAndRemainder(edu.jas.poly.GenPolynomial)" target="classFrame"><code>poly.GenPolynomial.divideAndRemainder</code></a>
</td>
<td>for univariate polynomials over fields
</td>
</tr>

<tr>
<td>2.3&nbsp;<code>EXTEUC</code></td>
<td><a href="doc/api/edu/jas/poly/GenPolynomial.html#egcd(edu.jas.poly.GenPolynomial)" target="classFrame"><code>poly.GenPolynomial.egcd</code></a>
</td>
<td>for univariate polynomials over fields
</td>
</tr>

<tr>
<td colspan="3">&nbsp;</td>
</tr>

<tr>
<td>3.1&nbsp;<code>LINDEP</code></td>
<td><a href="" target="classFrame"><code></code></a>
not implemented
</td>
<td>
</td>
</tr>

<tr>
<td>3.2&nbsp;<code>EXCHANGE</code></td>
<td><a href="" target="classFrame"><code></code></a>
not implemented
</td>
<td>
</td>
</tr>

<tr>
<td colspan="3">&nbsp;</td>
</tr>

<tr>
<td>4.1&nbsp;<code>EQUIV</code></td>
<td><a href="doc/api/edu/jas/structure/Residue.html#equals(java.lang.Object)" target="classFrame"><code>structure.Residue.equals</code></a>
or 
<a href="doc/api/edu/jas/application/Residue.html#equals(java.lang.Object)" target="classFrame"><code>application.Residue.equals</code></a>
</td>
<td>arbitrary residue class rings and residue class rings modulo polynomial ideals
</td>
</tr>

<tr>
<td colspan="3">&nbsp;</td>
</tr>

<tr>
<td>5.1&nbsp;<code>REDPOL</code></td>
<td><a href="doc/api/edu/jas/gb/Reduction.html#normalform(java.util.List,%20edu.jas.poly.GenPolynomial)" target="classFrame"><code>gb.Reduction.normalform</code></a>,
<a href="doc/api/edu/jas/gb/ReductionAbstract.html#normalform(java.util.List,%20java.util.List)" target="classFrame"><code>gb.ReductionAbstract.normalform</code></a>,
<a href="doc/api/edu/jas/gb/ReductionSeq.html#normalform(java.util.List,%20java.util.List,%20edu.jas.poly.GenPolynomial)" target="classFrame"><code>gb.ReductionSeq.normalform</code></a>
</td>
<td>interface and sequential computation class, the method exists also for
    polynomial lists and with a reduction recording matrix (this is exactly
    <code>REDPOL</code>)
</td>
</tr>

<tr>
<td>5.2&nbsp;<code>REDUCTION</code></td>
<td><a href="doc/api/edu/jas/gb/Reduction.html#irreducibleSet(java.util.List)" target="classFrame"><code>gb.Reduction.irreducibleSet</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td>5.3&nbsp;<code>GR&Ouml;BNERTEST</code></td>
<td><a href="doc/api/edu/jas/gb/GroebnerBase.html#isGB(java.util.List)" target="classFrame"><code>gb.GroebnerBase.isGB</code></a>
</td>
<td>provided by all classes which implement this interface
</td>
</tr>

<tr>
<td>5.4&nbsp;<code>GR&Ouml;BNER</code></td>
<td>not implemented
</td>
<td>
</td>
</tr>

<tr>
<td>5.5&nbsp;<code>REDGR&Ouml;BNER</code></td>
<td>not implemented
</td>
<td>
</td>
</tr>

<tr>
<td>5.6&nbsp;<code>GR&Ouml;BNERNEW1</code></td>
<td><a href="doc/api/edu/jas/gb/GroebnerBase.html#GB(java.util.List)" target="classFrame"><code>gb.GroebnerBase.GB</code></a>
</td>
<td>provided by all classes which implement the interface
</td>
</tr>

<tr>
<td>5.7&nbsp;<code>UPDATE</code>, 5.8&nbsp;<code>GR&Ouml;BNERNEW2</code></td>
<td>not implemented
</td>
<td>
</td>
</tr>

<tr>
<td>5.9&nbsp;<code>EXTGR&Ouml;BNER</code></td>
<td><a href="doc/api/edu/jas/gb/GroebnerBase.html#extGB(java.util.List)" target="classFrame"><code>gb.GroebnerBase.extGB</code></a>
</td>
<td>provided by some classes which implement the interface
</td>
</tr>

<tr>
<td colspan="3">&nbsp;</td>
</tr>

<tr>
<td>6.1&nbsp;<code>ELIMINATION</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#eliminate(edu.jas.poly.GenPolynomialRing)" target="classFrame"><code>application.Ideal.eliminate</code></a>
</td>
<td>the version with the <code>String[]</code> parameter only computes a Gr&ouml;bner base wrt. the 
respective elimination order
</td>
</tr>

<tr>
<td>6.2&nbsp;<code>PROPER</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#isONE()" target="classFrame"><code>application.Ideal.isONE</code></a>
</td>
<td>proper ideal test is <code>! id.isONE()</code>
</td>
</tr>

<tr>
<td>6.3&nbsp;<code>INTERSECTION</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#intersect(java.util.List)" target="classFrame"><code>application.Ideal.intersect</code></a>
</td>
<td>for lists of ideals a simple iterative algorithm is used and
for a pair of ideals it is the same algorithm
</td>
</tr>

<tr>
<td>6.4&nbsp;<code>CRT</code></td>
<td><a href="" target="classFrame"><code></code></a>
not implemented
</td>
<td>
</td>
</tr>

<tr>
<td>6.5&nbsp;<code>IDEALDIV1</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#quotient(edu.jas.application.Ideal)" target="classFrame"><code>application.Ideal.quotient</code></a>
</td>
<td>for an ideal a simple iterative algorithm is used and
for one polynomial it is an algorithm without computing syzygies
</td>
</tr>

<tr>
<td>6.6&nbsp;<code>IDEALDIV2</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#infiniteQuotientRab(edu.jas.poly.GenPolynomial)" target="classFrame"><code>application.Ideal.infiniteQuotientRab</code></a>
and 
<a href="doc/api/edu/jas/application/Ideal.html#infiniteQuotientExponent(edu.jas.poly.GenPolynomial)" target="classFrame"><code>application.Ideal.infiniteQuotientExponent</code></a>
</td>
<td>the exponent is computed in a separate step at the moment
</td>
</tr>

<tr>
<td>6.7&nbsp;<code>RADICALMEMTEST</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#isRadicalMember(edu.jas.poly.GenPolynomial)" target="classFrame"><code>application.Ideal.isRadicalMember</code></a>
</td>
<td>the exponent is not computed
</td>
</tr>

<tr>
<td>6.8&nbsp;<code>SUBRINGMEMTEST</code></td>
<td><a href="" target="classFrame"><code></code></a>
not implemented
</td>
<td>
</td>
</tr>

<tr>
<td colspan="3">&nbsp;</td>
</tr>

<tr>
<td>8.1&nbsp;<code>PREDEC</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#zeroDimDecomposition()" target="classFrame"><code>application.Ideal.zeroDimDecomposition</code></a>
</td>
<td>univariate polynomials of minimal degree in the ideal are irreducible 
and not a power of an irreducible polynomial as specified in <code>PREDEC</code>
</td>
</tr>

<tr>
<td>8.2&nbsp;<code>ZRADICALTEST</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#isZeroDimRadical()" target="classFrame"><code>application.Ideal.isZeroDimRadical</code></a>
</td>
<td>will also work in characteritsic p &gt; 0
</td>
</tr>

<tr>
<td>8.3&nbsp;<code>ZRADICAL</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#radical()" target="classFrame"><code>application.Ideal.radical</code></a>
</td>
<td><code>ZRADICAL</code> is containted as special case,
see also <a href="doc/api/edu/jas/application/Ideal.html#zeroDimRadicalDecomposition()" target="classFrame"><code>application.Ideal.zeroDimRadicalDecomposition</code></a>
</td>
</tr>

<tr>
<td>8.4&nbsp;<code>NORMPRIMDEC</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#zeroDimPrimaryDecomposition()" target="classFrame"><code>application.Ideal.zeroDimPrimaryDecomposition</code></a>
</td>
<td>contains all preprocessing steps, see <code>ZPRIMDEC</code>
</td>
</tr>

<tr>
<td>8.5&nbsp;<code>NORMPOS</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#normalPositionFor(int,%20int,%20java.util.List)" target="classFrame"><code>application.Ideal.normalPositionFor</code></a>
</td>
<td>one step of <code>NORMPOS</code> as explained for the modified algorithm on page 383ff
</td>
</tr>

<tr>
<td>8.6&nbsp;<code>ZPRIMDEC</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#zeroDimPrimaryDecomposition()" target="classFrame"><code>application.Ideal.zeroDimPrimaryDecomposition</code></a>
</td>
<td>returns a list of <code>PrimaryComponent</code> containers
</td>
</tr>

<tr>
<td>8.7&nbsp;<code>CONT</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#contraction(edu.jas.application.IdealWithUniv)" target="classFrame"><code>application.Ideal.contraction</code></a>
</td>
<td>more complicated since the permutation of variables must be considered also,
see <a href="doc/api/edu/jas/application/Ideal.html#permContraction(edu.jas.application.IdealWithUniv)" target="classFrame"><code>application.Ideal.permContraction</code></a>,
the polynomial <code>f</code> is returned in the <code>IdealWithUniv</code> container
</td>
</tr>

<tr>
<td>8.8&nbsp;<code>EXTCONT</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#extension(java.lang.String[])" target="classFrame"><code>application.Ideal.extension</code></a>
</td>
<td>only <code>EXT</code>, the combination <code>EXTCONT</code> is not implemented explicitly, 
the polynomial <code>f</code> is returned in the <code>IdealWithUniv</code> container
</td>
</tr>

<tr>
<td>8.9&nbsp;<code>RADICAL</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#radical()" target="classFrame"><code>application.Ideal.radical</code></a>
</td>
<td>for ideals with arbitrary dimension
</td>
</tr>

<tr>
<td>8.10&nbsp;<code>PRIMDEC</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#primaryDecomposition()" target="classFrame"><code>application.Ideal.primaryDecomposition</code></a>
</td>
<td>for ideals with arbitrary dimension
</td>
</tr>

<tr>
<td colspan="3"></td>
</tr>

<tr>
<td>8.11&nbsp;<code>VARSIGN</code></td>
<td><a href="doc/api/edu/jas/root/RootUtil.html#signVar(java.util.List)" target="classFrame"><code>root.RootUtil.signVar</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td>8.12&nbsp;<code>STURMSEQ</code></td>
<td><a href="doc/api/edu/jas/root/RealRootsSturm.html#sturmSequence(edu.jas.poly.GenPolynomial)" target="classFrame"><code>root.RealRootsSturm.sturmSequence</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td>8.13&nbsp;<code>ISOLATE</code></td>
<td>
<a href="doc/api/edu/jas/root/RealRoots.html#realRoots(edu.jas.poly.GenPolynomial)" target="classFrame"><code>root.RealRoots.realRoots</code></a>
</td>
<td>could also be used for real root isolations not using Sturm sequences
</td>
</tr>

<tr>
<td>8.14&nbsp;<code>ISOREC</code></td>
<td>
<a href="doc/api/edu/jas/root/RealRootsSturm.html#realRoots(edu.jas.root.Interval,%20java.util.List)" target="classFrame"><code>root.RealRootsSturm.realRoots</code></a>
</td>
<td>interval bi-section until a root is isolated
</td>
</tr>

<tr>
<td>8.15&nbsp;<code>ISOREFINE</code></td>
<td>
<a href="doc/api/edu/jas/root/RealRoots.html#refineInterval(edu.jas.root.Interval,%20edu.jas.poly.GenPolynomial,%20C)" target="classFrame"><code>root.RealRoots.refineInterval</code></a>
</td>
<td>also for real root isolations not using Sturm sequences
</td>
</tr>

<tr>
<td>8.16&nbsp;<code>SQUEEZE</code></td>
<td><a href="doc/api/edu/jas/root/RealRoots.html#invariantMagnitudeInterval(edu.jas.root.Interval,%20edu.jas.poly.GenPolynomial,%20edu.jas.poly.GenPolynomial,%20C)" target="classFrame"><code>root.RealRoots.invariantMagnitudeInterval</code></a>
</td>
<td>see also 
<a href="doc/api/edu/jas/root/RealRoots.html#realMagnitude(edu.jas.root.Interval,%20edu.jas.poly.GenPolynomial,%20edu.jas.poly.GenPolynomial,%20C)" target="classFrame"><code>root.RealRoots.realMagnitude</code></a>
</td>
</tr>

<tr>
<td>8.17&nbsp;<code>REALZEROS</code></td>
<td><a href="doc/api/edu/jas/application/PolyUtilApp.html#realAlgebraicRoots(edu.jas.application.Ideal)" target="classFrame"><code>application.PolyUtilApp.realAlgebraicRoots</code></a>
</td>
<td>different algorithm and different result data structure with <code>RealAlgebraicNumbers</code>
</td>
</tr>

<tr>
<td colspan="3">&nbsp;</td>
</tr>

<tr>
<td>9.1&nbsp;<code>REDTERMS</code></td>
<td><a href="doc/api/edu/jas/gbufd/GroebnerBaseFGLM.html#redTerms(java.util.List)" target="classFrame"><code>gbufd.GroebnerBaseFGLM.redTerms</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td>9.2&nbsp;<code>UNIVPOL</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#constructUnivariate(int)" target="classFrame"><code>application.Ideal.constructUnivariate</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td>9.3&nbsp;<code>CONVGR&Ouml;BNER</code></td>
<td><a href="doc/api/edu/jas/gbufd/GroebnerBaseFGLM.html#convGroebnerToLex(java.util.List)" target="classFrame"><code>gbufd.GroebnerBaseFGLM.convGroebnerToLex</code></a>
</td>
<td>
See also <a href="doc/api/edu/jas/gbufd/GroebnerBaseFGLM.html#GB(int, java.util.List)" target="classFrame"><code>gbufd.GroebnerBaseFGLM.GB</code></a>. It computes a Gr&ouml;bner base with respect to a graded term order and then uses FGLM to convert to a lexicographic term order
</td>
</tr>

<tr>
<td>9.4&nbsp;<code>LMINTERM</code></td>
<td><a href="doc/api/edu/jas/gbufd/GroebnerBaseFGLM.html#lMinterm(java.util.List, edu.jas.poly.GenPolynomial)" target="classFrame"><code>gbufd.GroebnerBaseFGLM.lMinterm</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td>9.5&nbsp;<code>STRCONST</code></td>
<td><a href="" target="classFrame"><code></code></a>
not implemented
</td>
<td>
</td>
</tr>

<tr>
<td>9.6&nbsp;<code>DIMENSION</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#dimension()" target="classFrame"><code>application.Ideal.dimension</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td colspan="3">&nbsp;</td>
</tr>

<tr>
<td>10.1&nbsp;<code>D-GR&Ouml;BNER</code></td>
<td><a href="doc/api/edu/jas/gb/DGroebnerBaseSeq.html#GB(int,%20java.util.List)" target="classFrame"><code>gb.DGroebnerBaseSeq.GB</code></a>
and 
<a href="doc/api/edu/jas/gb/EGroebnerBaseSeq.html#GB(int,%20java.util.List)" target="classFrame"><code>gb.EGroebnerBaseSeq.GB</code></a>
</td>
<td>
</td>
</tr>

</table>

<p>
</p>


<!--
<code></code> 
<p>
</p>
<p>
</p>
<pre>
</pre>
-->

<p><!--a href="README" target="readme" >README</a-->
<!--a href="" target="classFrame"><code></code></a-->
</p>

    <hr />
<address><a href="mailto:kredel at rz.uni-mannheim.de">Heinz Kredel</a></address>
<p>
<!-- Created: Sun May 23 13:14:59 CEST 2010 -->
<!-- hhmts start -->
Last modified: Sun Jul 15 19:12:04 CEST 2012
<!-- hhmts end -->
</p>
<!--p align="right" >
$Id$
</p-->
  </body>
</html>
